[APIO2010]-巡逻

https://vjudge.net/problem/HYSBZ-1912

题意：有 n 个村庄编号 1 ～ n ，有 n - 1 条双向道路连接它们，长度均为 1 个单位。编号为 1 的村庄里设立了警察局，巡警车每天从警察局出发，到所有的路上巡逻，最后回到警察局。每条道路都需要经过两次。现在为了减少总的巡逻距离，该地区准备在这些村庄之间建立 K 条新的道路，一条新道路甚至可以是一个环。由于资金有限，K 只能是 1 或 2。巡警车必须经过新建的道路正好一次。

不建立新的道路时，路线总长度为 2(n - 1) 。建立一条新道路后，因为新道路必须经过刚好一次，所以在沿着新道路 (x, y) 巡逻后，就必须沿着树上从 y 到 x 的路径巡逻一遍，最终形成一个环。相当于树上 x 与 y 之间的两条路径都只需经过一次了。

因此，当 K = 1 时，我们找到树的最长链（$L_1$），在两个端点之间加一条新道路，就是答案。若树的直径为 L ，答案就是 2(n - 1) - (L - 1) 。

当 K = 2 时，我们要再找一条最长链（$L_2$）。但这时如果两条新道路形成的环重叠，重叠部分就不会被巡逻到。但由于题目说每条道路必须被巡逻，所以在恰当的时刻重叠部分会被巡逻两遍，对答案没有贡献。

综上所述，我们得到如下算法：

1. 再最初的树上求直径，记为 $L_1$ ，然后把直径上的标记取反（从 1 改为 -1）；
2. 再最长链标记取反的树上再次求直径，记为 $L_2$ 。

答案就是 $2(n - 1) - (L_1 - 1) - (L_2 - 1)$ 。

为什么取反能正确处理重叠部分呢？

因为如果 $L_2$ 包含 $L_1$ 取反的部分，就相当于两个环重叠，最初重叠的部分需要经过两次；减掉 $L_1 - 1$ 后，重叠的部分变成了只需经过一次；减掉 $L_2 - 1$ 后，负负得正，相当于把重叠的部分加回来，变回了“需要经过两次”。

$O(n)$

这题主要是注意 dfs 取树直径部分的代码，还有记录直径的方法，思维上注意取反抵消的方法。

CODE：

#include <bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;

int n, K, tot, cnt = 1, dia, mx;
int lnk[N];
int s1[N], s2[N];  // 存第一次树直径的路径
struct edge {
    int to, next, v;
}e[2 * N];

void add(int u, int v) {
    e[++cnt].to = v, e[cnt].next = lnk[u], lnk[u] = cnt, e[cnt].v = 1;
    e[++cnt].to = u, e[cnt].next = lnk[v], lnk[v] = cnt, e[cnt].v = 1;
}

int dfs(int x, int fa) {
    int mx1 = 0, mx2 = 0;
    for (int i = lnk[x]; i; i = e[i].next)
        if (e[i].to != fa) {
            int v = e[i].v + dfs(e[i].to, x);
            if (v > mx1) mx2 = mx1, mx1 = v, s2[x] = s1[x], s1[x] = i;
            else if (v > mx2) mx2 = v, s2[x] = i;
        }
    if (mx1 + mx2 > dia) dia = mx1 + mx2, mx = x;
    return mx1;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> K;
    tot = 2 * (n - 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
    }
    dfs(1, 0);
    tot = tot - dia + 1;
    if (K == 2) {
        dia = 0;
        for (int i = s1[mx]; i; i = s1[e[i].to]) e[i].v = e[i ^ 1].v = -1;
        for (int i = s2[mx]; i; i = s1[e[i].to]) e[i].v = e[i ^ 1].v = -1;
        dfs(1, 0);
        tot = tot - dia + 1;
    }
    cout << tot << endl;
    return 0;
}